package baseclass.a_sort.quickSort;


import baseclass.a_sort.ArraysTool;

import java.util.Arrays;

/**
 * @date 2020/2/26 20:03
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-4, -8, 4, 8, -6, -3, -7, -5};
        quick(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quick(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        doQuick(arr, 0, arr.length - 1);
    }

    private static void doQuick(int[] arr, int l, int r) {
        if (l >= r) return;
        int[] range = partition(arr, l, r);
        doQuick(arr, l, range[0] - 1);
        doQuick(arr, range[1] + 1, r);
    }

    private static int[] partition(int[] arr, int l, int r) {
        int target = arr[l + (int) (Math.random() * (r - l + 1))];
//        int target = arr[r];
        int less = l - 1;
        int more = r + 1;
        int p = l;
        while (p < more) {
            if (arr[p] < target) {
                ArraysTool.swap(arr, ++less, p++);
            } else if (arr[p] > target) {
                ArraysTool.swap(arr, --more, p);
            } else {
                p++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
}
